package com.LeetCodeT.Greedy;

import org.junit.jupiter.api.Test;

import java.util.*;
import java.util.stream.Collectors;
// -*- coding: utf-8 -*-

/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-03 19:18
 * IDE: IntelliJ IDEA
 * Introduction:
 */
public class MinSubsequence {
    public List<Integer> minSubsequence(int[] nums) {
        // 返回最小非递增大于剩下预算
        List<Integer> digits = Arrays.stream(nums).boxed().sorted(Collections.reverseOrder()).collect(Collectors.toList());
        ArrayList<Integer> ans = new ArrayList<>();
        Integer sum = digits.stream().reduce(Integer::sum).get();
        int tmp = 0;
        while (digits.size() > 0) {
            int t = digits.remove(0);
            tmp += t;
            ans.add(t);
            if (sum - tmp < tmp) {
                // 获取最小连续序列
                return ans;
            }
        }
        return ans;
    }


    @Test
    public void shout() {
        int[] nums = {4, 3, 10, 9, 8};
        System.out.println(minSubsequence(nums));
    }
}
